class Solution(object):
    def findKthBit(self, n, k):
        def create(n):
            if n == 1:
                return [0]
            else:
                last = create(n - 1)
                last_v = list(reversed(last))
                last_v = [1 - item for item in last_v]
                return last + [1] + last_v

        return str(create(n)[k - 1])

data = Solution()
n = 3
k = 1
print(data.findKthBit(n, k))